This invention has been created without the sponsorship or funding of any federally sponsored research or development program.
1. Field of the Invention
This invention relates to cryptographic communication in general, and more specifically, to methods and apparatus for securely proving knowledge of a shared small secret password between two parties using messages exchanged across an open communication channel.
1. Description of the Related Art
Passwords are an essential component of secure systems. Although they play a crucial role in authenticating the identity of people to systems, traditional password-based network authentication systems have weaknesses due to improper use of passwords. Such systems often use the password as if it were a cryptographic key, and require the password to be chosen as carefully as one would choose a cryptographic key. One requirement is that the choice be from an effectively large xe2x80x9cpassword-spacexe2x80x9d. The size of this space is sometimes expressed in terms of a number of bits of xe2x80x9centropyxe2x80x9d. For simplicity, we often refer to any low-entropy secret from a space that is vulnerable to dictionary attacks as a xe2x80x9csmall passwordxe2x80x9d. In practice, due to human limitations, many passwords are small. This is a problem for many systems which can be attacked using a repeated computation using all possible (or likely) guesses for the password. This is known as a brute-force, or dictionary attack.
Dictionary attacks can occur on-line, in an interaction between an attacker and a legitimate user or system. They can also occur off-line, using information gathered by monitoring messages sent between two legitimate parties during an authentication protocol exchange. On-line attacks can often be easily detected and thwarted, by counting bad attempts and denying access. Banking ATM machines thwart attack by retaining the user""s card after three bad access attempts. But remote authentication opens the possibility of an off-line attack on the messages transmitted across a network.
As widely available computing power increases, successful off-line dictionary attacks on a small password become easier. Today, ever-increasing computer power has clearly outpaced the (unchanging) ability of people to remember longer passwords. Today, 56-bit symmetric key seem to offer only marginal security. U.S. export regulations have allowed export of 40-bit key systems, presumably because they are breakable. Thus, in many systems, a xe2x80x9csafely large passwordxe2x80x9d requires more than 40 bits of entropy, and the number is steadily growing. On the other hand, it seems that many people cannot easily remember and use a password from a space of 32 bits. This is equivalent to a random 10 digit number, about 6 random letters and digits, or a pair of words from an average English dictionary. Several studies over many years have found that a significant percentage of user-chosen passwords can be found with a modest computational effort, having an effective size of less than 30 bits (roughly a billion choices). At one extreme, bank-card PIN numbers have less than 14 bits. Forcing everyone to double or triple the size of their passwords, and expecting them to not write them down, or expecting most people to be comfortable using xe2x80x9cpass-phrasesxe2x80x9d, is denying the inevitable truth. People can""t or won""t properly handle anything larger than a small password, so systems must protect them from attack. In light of this, most traditional network authentication systems that use passwords are obsolete. Better systems must be designed and deployed that are resistant to off-line dictionary attack, to safely tolerate the use of potentially small passwords.
Detailed Objective
Our goal is to authenticate one party to the other with a series of messages exchanged across an open network, where interception or modification of the messages by an untrusted third party may be possible. Furthermore, we do not require that either party have access to any additional long-lived keys for either a symmetric or a public-key encryption systemxe2x80x94we seek a method based solely on the password. In light of the crucial role of the password, we must protect it as much as possible.
These methods can be used for direct person-to-person authentication, where an appropriate computer or device performs the required protocol computation on behalf of the person. More typically, one of the parties is a host computer. We will refer to the user""s computer as xe2x80x9cAlicexe2x80x9d and the host computer as xe2x80x9cBobxe2x80x9d.
We assume that Alice and Bob use a small password as the basis for establishing a secure communication channel between the them, and we assume that an attacker has the computational power to enumerate all possible password values to attempt a dictionary attack. We first desire a method where Alice and Bob prove to each other that they know the same secret. We also desire an extended method where Bob, who only has knowledge of a xe2x80x9chidden-passwordxe2x80x9d, verifies that Alice knows the password. The hidden-password in our extended method will be a specially constructed one-way transformation of the password.
Historically, much attention has focused on the problem of getting Alice to use a large xe2x80x9cwell-chosenxe2x80x9d password. Newer research, such as ours, focuses attention on how to legitimately use a small password for remote authentication across an open insecure network. This must be done without making the password vulnerable to off-line dictionary attack.
Traditional Methods
Most older methods of remote authentication based on a shared secret do not survive dictionary attacks when the secret is small. In a common example, Alice sends a random number R to Bob, Bob computes a one-way collision-free hash function h of both R and the password S, and sends the result h(R,S) to Alice. Alice also computes h(R,S) and compares it to Bob""s result. If they are equal, Bob has proven knowledge of the password to Alice, and because of the hash, the secret password is not directly revealed to a third party who monitors the exchange. The randomness of R prevents replay attacks. However, when the password is small, Eve, an eavesdropper who obtains R and h(R,S), can repeatedly hash each possible password Sxe2x80x2 in the dictionary with R, and compare each result h(R,Sxe2x80x2) to Bob""s response. (The dictionary entries may be either pre-built, or computed as needed.) When a match is found, the attacker knows that Sxe2x80x2 is the password.
When tolerance for small passwords is added to all the classic requirements for a secure exchange, most traditional password authentication methods are shown to be obsolete.
Some methods can confirm knowledge of a small shared secret based on the parties"" access to other long-lived data. This data may be a large shared secret, or a large public key. There are many general methods for public-key-based authentication. Such schemes pose additional problems such as certifying public-keys, requiring a secure key distribution system, or requiring secure storage for large secret keys. Here we seek methods that are based solely on an easily-memorized secret.
Minimal Disclosure Methods
A few methods exist that address our goal of preventing off-line dictionary attacks, without requiring access to additional long-lived keys. Examples are the various Encrypted Key Exchange (EKE) methods described by Bellovin and Merritt [BM92] and the xe2x80x9csecret public-keyxe2x80x9d methods described by Gong and others in [GLSN93, Gon95]. An example of an enhancement where Bob stores a one-way function of the password, and verifies that Alice knows the original password, are the A-EKE methods described in [BM94]. These documents are herein incorporated by reference. These methods represent the best of the prior art, and reveal little or no information for an attacker to mount a dictionary attack. We will call these xe2x80x9cminimal disclosurexe2x80x9d methods, since they minimize disclosure of information about the password to potential attackers.
Another method that is somewhat resistant to passive dictionary attack is called Fortified Key Negotiation (FKN), and is described in [AL94]. We refer to this as a xe2x80x9creduced disclosurexe2x80x9d method, since it may leak a considerable amount of information.
These minimal disclosure methods are relatively new, and have not yet been widely deployed in applications.
Diffie-Hellman Exponential Key Exchange
A common function used in modern cryptographic methods is the Diffie-Hellman exponential key exchange (xe2x80x9cDHxe2x80x9d) described in [DH79]. This is an example of a public-key distribution system, the purpose of which is to distribute keys to one or more parties using some kind of public-key technique. This is different than a public-key cryptosystem the purpose of which is to typically perform signing and/or sealing operations.
The major limitation of original DH is that it is an unauthenticated public-key exchangexe2x80x94It doesn""t prove the identity of either party to the other. It is thus vulnerable to a xe2x80x9cman-in-the-middle attack where a third party, Mallory, performs two distinct DH exchanges with Alice and Bob to create separate encrypted channels. By decrypting and re-encrypting all messages passed between Alice and Bob, Mallory can act as an undetected eavesdropper. Despite this limitation, DH has important uses and the basic computation in DH forms a basis for many well-known security schemes, such as the ElGamal and related public-key crypto-systems, the DSS digital signature standard [NIST94]. Two methods that have incorporated DH to provide an authenticated key exchange are the Station-to-Station protocol and DH-EKE, one of the Encrypted Key Exchange methods. Our methods will also utilize a DH exchange.
The general construction of DH uses exponentiation within a mathematical group. Although a variety of groups can be used in DH, a common example uses arithmetic in Zp*, the multiplicative group of the Galois field of integers modulo p, where p is a large prime. Zp* is also sometimes written as GF(p)*. The elements (members) of this group are the integers from 1 to pxe2x88x921, and the group operator (represented by *) is multiplication modulo p. We review the classic DH operation here:
g and p are well-known numbers, where g is a primitive root of p.
Bob chooses a random RB, computes QB=gRB mod p, and sends QB to Alice.
Alice chooses a random RA, computes QA=gRA mod p, and send QA to Bob.
Bob computes K=QARB mod p.
Alice computes K=QBRA mod p.
The result of the exchange is that both Alice and Bob alone share knowledge of a large key K. They both compute the same value of K because (gRA)RB mod p=(gRB)RA mod p.
DH can also use other groups, including large prime-order subgroups of Zp*, and groups of points on elliptic curves over finite fields. The principal advantage of alternate groups such as elliptic curves lies in their increased resistance to a discrete-log computation for a given computational cost, assuming the current knowledge of discrete log techniques. With elliptic curve groups, the size of the field can be much smaller than the size required with Zp*, and thus fewer bits are needed to represent the group elements.
We will use the term xe2x80x9cexponentiationxe2x80x9d to broadly refer to repeated applications of the group operator on an element with itself. In some cases, the group operator does not use exponential arithmetic in the integers. For example, the literature on elliptic curve groups traditionally describes the group operator for two points as xe2x80x9cadditionxe2x80x9d of points, and group exponentiation to an integer power is described as xe2x80x9cmultiplication of a point by an integerxe2x80x9d. Further description of elliptic curve groups can be found in [P1363).
Though our discussion will focus on Zp* and it""s subgroups, the techniques we will discuss apply to use of DH in any other suitable group with comparable structure. We now briefly review some algebraic results that are relevant to use of the DH in both our method as well as in DH-EKE.
Selection of DH Parameters g and p, and the Structure of Zp*
The first DH computation (using Zp*) is gR mod p, where g and p are specially chosen, and R is a large random number. Proper selection of g and p is crucial to the DH exponential key exchange, in general, and even more so in password-authenticated DH methods. We will generally limit our discussion to groups where the factorization of pxe2x88x921 is known, and where pxe2x88x921 has a large prime factor q. A large prime factor prevents easy solutions to the discrete logarithm problem, and methods to generate such values of p with several hundreds and even thousands of bits are well known to those skilled in the art. It has been recommended that the sizes of R and q be at least twice the number of bits needed in the resulting key. The size of p must generally be much larger resist long-term attack on discrete logs in Zp*.
Throughout the discussion we use the abbreviated notation xe2x80x9cxzxe2x80x9d to mean exponentiation within some DH group. With respect to Zp*, xe2x80x9cxzxe2x80x9d is equivalent to (x raised to the power z) mod pxe2x80x9d. We will also refer to subgroups of Zp* as Gx, where x is the order of the group.
The literature [PH78, McC90] discusses the proper selection of g and p, in particular to address the concern that easier solutions to the discrete logarithm problem make it easier to attack DH. Classical values for p and g in DH are where p=2q+1, q is also a large prime, and g is a primitive root of p. It has also been recommended to use values for g in DH that are generators of a smaller but still large subgroup of Zp* [P1363]. However, the available literature does not discuss how the structure of the group is particularly relevant to authentication systems that use DH. We explore this further in the detailed description of our invention.
In both [BM92] and [STW95] we find some analysis of the security of DH-EKE. [BM92] warns against allowing 0 to be used as an exponent. Attacks using other special numbers were, at that time, unknown. A variation of DH-EKE named M-EKE and general techniques for refining and strengthening the protocol against certain attacks are discussed in [STW95]. In the course of our invention, we uncovered a flaw in DH-EKE as described in the available literature. An analysis of this flaw and a means for correcting it are included in our method.
The inventions described establish a large mutually-authenticated shared secret key between parties over an open insecure channel, where the authentication is based solely on mutual possession of a potentially small shared secret, such as a password.
The methods are different from the prior art, and constitute an improvement by eliminating steps and constraints which are required in prior methods to keep them free from attack. These new methods may permit more efficient implementations than the prior art.
The first method is a simplified password-authenticated exponential key exchange (SPEKE) where a function of the password determines the parameters of a public-key distribution system, such as a Diffie-Hellman (xe2x80x9cDHxe2x80x9d) key exchange. SPEKE is comparable to the DH-Encrypted Key Exchange method, but is different in that no symmetric encryption steps are used. The parties"" success in establishing a common DH key is used to prove knowledge of the shared secret by one party to another.
An extended hidden-password verification (xe2x80x9cHVERxe2x80x9d) method is also described whereby one of the parties uses a stored one-way function of the password, called the xe2x80x9chidden passwordxe2x80x9d to authenticate knowledge of the original password by another. This method is used in conjunction with another authenticated key exchange, such as SPEKE or DH-EKE, and represents an alternative to prior extended methods such as A-EKE.
In HVER, the user creates a long-lived DH integer exponent C based on the password. A DH base g, and a DH exponential gC is computed. The pair of values {g, gC} represents the user""s hidden password, which is maintained as a shared secret and stored securely with the host. In HVER authentication, a SPEKE (or equivalent) exchange is first performed using gC as the shared secret basis, resulting in a shared key K1. Then a second DH exchange is completed where the host chooses a random exponent X, and sends the value of gX to the user. Both compute a second shared key K2=g(X C). The user then proves knowledge of the combined values of K1 and K2 to the host, thereby proving knowledge of the password C. The usual problems associated with a low-entropy DH exponent C are resolved by protecting the host""s storage of gC, and by the simultaneous proof of K2 with the previously authenticated K1.
Objectives
It is an object of this invention to allow one party to verify that another party has knowledge of a small password by exchanging messages.
It is an object of this invention to allow the exchange to be performed over an insecure communication channel.
It is an object of this invention to not require the user to store any large long-lived secret data, such as cryptographic secret keys, public keys, or certificates.